/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
   @Language: C++
   @Datetime: 19-07-15 16:12
   */

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
	TreeNode *postordered(vector<int> &inorder, vector<int> &postorder, int begin, int end, int &pos){
		if(pos<0 || begin>=end) return NULL;
		TreeNode *r= new TreeNode(postorder[--pos]);
		int cur=0;
		for(cur=begin; cur<end && inorder[cur]!=r->val; ++cur);
		r->right=postordered(inorder,postorder,cur+1,end,pos);
		r->left=postordered(inorder,postorder,begin,cur,pos);
		return r;
	}
public:
	TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
		int pos=postorder.size();
		return postordered(inorder,postorder,0,inorder.size(),pos);
	}
};
